package com.lw.leetcode.linked.c;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 1851. 包含每个查询的最小区间
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/17 17:56
 */
public class MinInterval {

    public static void main(String[] args) {
        MinInterval test = new MinInterval();

        // {3,3,1,4}
        int[][] intervals = {{1, 4}, {2, 4}, {3, 6}, {4, 4}};
        int[] queries = {2, 3, 4, 5};

        // [2,-1,4,6]
//        int[][] intervals = {{2, 3}, {2, 5}, {1, 8}, {20, 25}};
//        int[] queries = {2, 19, 5, 22};

        // [4,3,6,3,6]
//        int[][] intervals = {{4, 5}, {5, 8}, {1, 9}, {8, 10}, {1, 6}};
//        int[] queries = {7, 9, 3, 9, 3};

        int[] ints = test.minInterval(intervals, queries);
        System.out.println(Arrays.toString(ints));

    }

    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int l = intervals.length;
        int length = queries.length;
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            arr[i][0] = queries[i];
            arr[i][1] = i;
        }
        Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
        Node root = new Node(Integer.MAX_VALUE, 0);
        Node end = new Node(0, 0);
        root.next = end;
        end.pre = root;
        TreeMap<Integer, Node> map = new TreeMap<>();
        int index = 0;
        int[] values = new int[length];
        for (int[] ints : arr) {
            int val = ints[0];
            Node item = end.pre;
            Node pre = item.pre;
            while (item.val < val) {
                map.remove(item.val);
                pre.next = end;
                end.pre = pre;
                item.next = null;
                item.pre = null;
                item = pre;
                pre = item.pre;
            }
            while (index < l && intervals[index][0] <= val) {
                int a = intervals[index][0];
                if (a > val) {
                    break;
                }
                int b = intervals[index][1];
                index++;
                if (b < val) {
                    continue;
                }
                int c = b - a + 1;
                Node node = new Node(b, c);
                if (end.pre.val > b) {
                    pre = end.pre;
                    pre.next = node;
                    node.pre = pre;
                    node.next = end;
                    end.pre = node;
                } else {
                    Map.Entry<Integer, Node> en = map.floorEntry(b);
                    pre = en.getValue().pre;
                    item = pre.next;
                    while (item.count >= c) {
                        map.remove(item.val);
                        Node next = item.next;
                        pre.next = next;
                        next.pre = pre;
                        item.next = null;
                        item.pre = null;
                        item = next;
                    }
                    pre.next = node;
                    node.pre = pre;
                    node.next = item;
                    item.pre = node;
                }
                map.put(b, node);
            }
            item = end.pre;
            if (item.val == Integer.MAX_VALUE) {
                values[ints[1]] = -1;
            } else {
                values[ints[1]] = item.count;
            }
        }
        return values;
    }

    private class Node {
        private int val;
        private int count;
        private Node next;
        private Node pre;

        public Node(int val, int count) {
            this.val = val;
            this.count = count;
        }
    }

}
